GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>K-Means-Algorithmus</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">k-Means-Algorithmus</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Ein k-Means-Algorithmus ist ein Verfahren zur <a href="Vektorquantisierung" title="Vektorquantisierung">Vektorquantisierung</a>, das auch zur <a href="Clusteranalyse" title="Clusteranalyse">Clusteranalyse</a> verwendet wird. Dabei wird aus einer Menge von ähnlichen Objekten eine vorher bekannte Anzahl von k Gruppen gebildet. Der Algorithmus ist eine der am häufigsten verwendeten Techniken zur Gruppierung von Objekten, da er schnell die Zentren der Cluster findet. Dabei bevorzugt der Algorithmus Gruppen mit geringer Varianz und ähnlicher Größe.

Der <a href="Algorithmus" title="Algorithmus">Algorithmus</a> hat starke Ähnlichkeiten mit dem <a href="EM-Algorithmus" title="EM-Algorithmus">EM-Algorithmus</a> und zeichnet sich durch seine Einfachheit aus.<a href="#cite_note-OpenCV.479-1">[1]</a>

Erweiterungen sind der k-Median-Algorithmus und der k-Means++ Algorithmus.

<div class="mw-heading mw-heading2"><h2 id="Historische_Entwicklung">Historische Entwicklung</h2></div>

Der Begriff „k-means“ wurde zuerst von MacQueen 1967 verwendet,<a href="#cite_note-macqueen1967-2">[2]</a> die Idee geht jedoch auf <a href="Hugo_Steinhaus" title="Hugo Steinhaus">Hugo Steinhaus</a> 1957 zurück.<a href="#cite_note-Steinhaus.801-804-3">[3]</a> Der heutzutage meist als „k-means-Algorithmus“ bezeichnete Standard-Algorithmus wurde 1957 von Lloyd zur <a href="Puls-Code-Modulation" title="Puls-Code-Modulation">Puls-Code-Modulation</a> vorgeschlagen, aber erst 1982 in einer Informatik-Zeitschrift publiziert<a href="#cite_note-lloyd1957-4">[4]</a> und deckt sich weitestgehend mit der Methode von Forgy, die 1965 publiziert wurde.<a href="#cite_note-forgy65-5">[5]</a> Eine weitere Variante ist die von Hartigan und Wong, die unnötige Distanzberechnungen vermeidet, indem sie auch den Abstand zum zweitnächsten Mittelpunkt verwendet.<a href="#cite_note-hartigan1975-6">[6]</a><a href="#cite_note-hartigan1979-7">[7]</a> Die Algorithmen werden den genannten Personen oft falsch zugeordnet: Insbesondere wird oft der Algorithmus von Lloyd/Forgy beschrieben, als Quelle jedoch MacQueen genannt.

<div class="mw-heading mw-heading2"><h2 id="Problemstellung">Problemstellung</h2></div>

Ziel von k-Means ist es, den Datensatz so in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> Partitionen zu teilen, dass die Summe der quadrierten Abweichungen von den Cluster-Schwerpunkten minimal ist. Mathematisch entspricht dies der Optimierung der Funktion

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle J=\sum _{i=1}^{k}\sum _{\mathbf {x} _{j}\in S_{i}}{\|\mathbf {x} _{j}-{\boldsymbol {\mu }}_{i}\|^{2}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/baecba31ac1960c0de8cea1c2e3ffc815871754f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.671ex; width:24.125ex; height:8.009ex;" alt="{\displaystyle J=\sum _{i=1}^{k}\sum _{\mathbf {x} _{j}\in S_{i}}{\|\mathbf {x} _{j}-{\boldsymbol {\mu }}_{i}\|^{2}}}" loading="lazy"></dd></dl>

mit den Datenpunkten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {x} _{j}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {x} _{j}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/da7e57d3f8c537992b45488f9586aec0c35a85f0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.321ex; height:2.343ex;" alt="{\displaystyle \mathbf {x} _{j}}" loading="lazy"> und den <a href="Mittelwert" title="Mittelwert">Schwerpunkten</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {\mu }}_{i}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {\mu }}_{i}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1fb8eff83748a7c926b7fb0774c469d6dd949a5d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.445ex; height:2.176ex;" alt="{\displaystyle {\boldsymbol {\mu }}_{i}}" loading="lazy"> der Cluster <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{i}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/de6e810a93f67802ecb603ee0e3324005c6e583e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.225ex; height:2.509ex;" alt="{\displaystyle S_{i}}" loading="lazy">.

Diese Zielfunktion basiert auf der <a href="Methode_der_kleinsten_Quadrate" title="Methode der kleinsten Quadrate">Methode der kleinsten Quadrate</a> und man spricht auch von Clustering durch Varianzminimierung,<a href="#cite_note-Ester,Sander-8">[8]</a> da die Summe der Varianzen der Cluster minimiert wird. Da zudem <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \|\mathbf {x} _{j}-{\boldsymbol {\mu }}_{i}\|^{2}}">

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \|\mathbf {x} _{j}-{\boldsymbol {\mu }}_{i}\|^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/104bd0de5439f0a94e116fa92252b760245f6552.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:10.985ex; height:3.343ex;" alt="{\displaystyle \|\mathbf {x} _{j}-{\boldsymbol {\mu }}_{i}\|^{2}}" loading="lazy"> die quadrierte <a href="Euklidische_Distanz" class="mw-redirect" title="Euklidische Distanz">Euklidische Distanz</a> ist, ordnet k-Means effektiv jedes Objekt dem nächstgelegenen (nach Euklidischer Distanz) Clusterschwerpunkt zu. Umgekehrt ist das arithmetische Mittel ein <a href="Methode_der_kleinsten_Quadrate" title="Methode der kleinsten Quadrate">Kleinste-Quadrate-Schätzer</a>, optimiert also ebenfalls dieses Kriterium.

<div class="mw-heading mw-heading2"><h2 id="Algorithmen">Algorithmen</h2></div>

Da die Suche nach der optimalen Lösung schwer ist (<a href="NP-Schwere" title="NP-Schwere">NP-schwer</a>), wird im Normalfall ein approximativer Algorithmus verwendet wie die Heuristiken von Lloyd oder MacQueen. Da die Problemstellung von k abhängig ist, muss dieser Parameter vom Benutzer festgelegt werden. Es existieren jedoch auch Ansätze, durch Verwendung eines zweiten Objektes diesen Parameter zu wählen (vgl. X-Means, <a href="Akaike-Informationskriterium" class="mw-redirect" title="Akaike-Informationskriterium">Akaike-Informationskriterium</a>, <a href="Bayessches_Informationskriterium" class="mw-redirect" title="Bayessches Informationskriterium">bayessches Informationskriterium</a> und <a href="Silhouettenkoeffizient" title="Silhouettenkoeffizient">Silhouettenkoeffizient</a>).

<div class="mw-heading mw-heading3"><h3 id="Lloyd-Algorithmus">Lloyd-Algorithmus</h3></div>

Der am häufigsten verwendete k-Means-Algorithmus ist der Lloyd-Algorithmus, der oft als „der k-means-Algorithmus“ bezeichnet wird, obwohl Lloyd diesen Namen nicht verwendet hat. Lloyds Algorithmus besteht aus drei Schritten:

<ol><li>Initialisierung: Wähle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> zufällige Mittelwerte (Means): <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {m} _{1}^{(1)},\ldots ,\mathbf {m} _{k}^{(1)}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {m} _{1}^{(1)},\ldots ,\mathbf {m} _{k}^{(1)}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1faa5665db2fecc3d01cf2840f687b387c0ba420.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:14.298ex; height:3.676ex;" alt="{\displaystyle \mathbf {m} _{1}^{(1)},\ldots ,\mathbf {m} _{k}^{(1)}}" loading="lazy"> aus dem Datensatz.</li>

<li>Zuordnung: Jedes Datenobjekt wird demjenigen Cluster zugeordnet, bei dem die Cluster-Varianz am wenigsten erhöht wird. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{i}^{(t)}=\left\{\mathbf {x} _{j}:{\big \|}\mathbf {x} _{j}-\mathbf {m} _{i}^{(t)}{\big \|}^{2}\leq {\big \|}\mathbf {x} _{j}-\mathbf {m} _{i^{*}}^{(t)}{\big \|}^{2}{\text{ für alle }}i^{*}=1,\ldots ,k\right\}}">

</mrow>

</mrow>

</msubsup>

<mrow>

<mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</msubsup>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msubsup>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{i}^{(t)}=\left\{\mathbf {x} _{j}:{\big \|}\mathbf {x} _{j}-\mathbf {m} _{i}^{(t)}{\big \|}^{2}\leq {\big \|}\mathbf {x} _{j}-\mathbf {m} _{i^{*}}^{(t)}{\big \|}^{2}{\text{ für alle }}i^{*}=1,\ldots ,k\right\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2886e84dcfff67ee62a2b356ca8819b8a73f6505.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:63.704ex; height:4.843ex;" alt="{\displaystyle S_{i}^{(t)}=\left\{\mathbf {x} _{j}:{\big \|}\mathbf {x} _{j}-\mathbf {m} _{i}^{(t)}{\big \|}^{2}\leq {\big \|}\mathbf {x} _{j}-\mathbf {m} _{i^{*}}^{(t)}{\big \|}^{2}{\text{ für alle }}i^{*}=1,\ldots ,k\right\}}" loading="lazy"></li>

<li>Aktualisieren: Berechne die Mittelpunkte der Cluster neu: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {m} _{i}^{(t+1)}={\frac {1}{|S_{i}^{(t)}|}}\sum _{\mathbf {x} _{j}\in S_{i}^{(t)}}\mathbf {x} _{j}}">

</mrow>

</mrow>

</mrow>

</msubsup>

<mfrac>

<mrow>

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mfrac>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</munder>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {m} _{i}^{(t+1)}={\frac {1}{|S_{i}^{(t)}|}}\sum _{\mathbf {x} _{j}\in S_{i}^{(t)}}\mathbf {x} _{j}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cdd16cba1836f523f4f11d149ac3826598506c5e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.505ex; width:23.951ex; height:7.843ex;" alt="{\displaystyle \mathbf {m} _{i}^{(t+1)}={\frac {1}{|S_{i}^{(t)}|}}\sum _{\mathbf {x} _{j}\in S_{i}^{(t)}}\mathbf {x} _{j}}" loading="lazy"></li></ol>

Die Schritte 2–3 werden dabei so lange wiederholt, bis sich die Zuordnungen nicht mehr ändern.

<div class="mw-heading mw-heading3"><h3 id="MacQueen’s_Algorithmus">MacQueen’s Algorithmus</h3></div>

MacQueen führte mit dem Begriff „k-Means“ einen anderen Algorithmus ein:

<ol><li>Wähle die ersten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> Elemente als Clusterzentren</li>

<li>Weise jedes neue Element dem Cluster zu, bei dem sich die Varianz am wenigsten erhöht, und aktualisiere das Clusterzentrum</li></ol>

Während es ursprünglich – vermutlich – nicht vorgesehen war, kann man auch diesen Algorithmus iterieren, um ein besseres Ergebnis zu erhalten.

<div class="mw-heading mw-heading3"><h3 id="Variationen">Variationen</h3></div>

<ul><li>k-Means ++ versucht, bessere Startpunkte zu finden.<a href="#cite_note-9">[9]</a></li>

<li>Der Filtering-Algorithmus verwendet als <a href="Datenstruktur" title="Datenstruktur">Datenstruktur</a> einen <a href="K-d-Baum" title="K-d-Baum">k-d-Baum</a>.<a href="#cite_note-10">[10]</a></li>

<li>Der k-Means-Algorithmus kann beschleunigt werden unter Berücksichtigung der <a href="Dreiecksungleichung" title="Dreiecksungleichung">Dreiecksungleichung</a>.<a href="#cite_note-Elkan-11">[11]</a></li>

<li>Bisecting k-means beginnt mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0bd301789e1f25a3da4be297ff637754ebee5f5d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.472ex; height:2.176ex;" alt="{\displaystyle k=2}" loading="lazy">, und teilt dann immer den größten Cluster, bis das gewünschte k erreicht ist.</li>

<li>X-means beginnt mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0bd301789e1f25a3da4be297ff637754ebee5f5d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.472ex; height:2.176ex;" alt="{\displaystyle k=2}" loading="lazy"> und erhöht <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> so lange, bis sich ein sekundäres Kriterium (Akaike-Informationskriterium, oder bayessches Informationskriterium) nicht weiter verbessert.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Voraussetzungen">Voraussetzungen</h2></div>

k-Means optimiert die quadratischen Abweichungen von einem Mittelwert. Es kann daher nur mit numerischen Attributen verwendet werden, bei denen ein sinnvoller Mittelwert berechnet werden kann. Kategorielle Attribute (bspw. „Auto“, „LKW“, „Fahrrad“) können nicht verwendet werden, da hier kein Mittelwert berechnet werden kann.

Der Parameter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">, die Anzahl der Cluster, muss im Voraus bekannt sein. Er kann jedoch auch experimentell bestimmt werden. Das Problem ist, dass die verschiedenen Cluster miteinander verglichen werden müssen und die Kostenfunktion mit steigendem <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> monoton sinkt. Eine Lösung ist der <a href="Silhouettenkoeffizient" title="Silhouettenkoeffizient">Silhouettenkoeffizient</a>, der eine von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> unabhängige Bewertung von Clusterungen liefert. Hierbei wird nicht nur geprüft, wie weit ein Punkt vom eigenen Clusterschwerpunkt entfernt ist, sondern es gehen auch die Entfernungen von anderen Clusterschwerpunkten in die Bewertung des Clustering mit ein.

Die Cluster im Datensatz müssen etwa gleich groß sein, da der Algorithmus den Datensatz stets an der Mitte zwischen zwei Clusterzentren partitioniert.

Der Datensatz darf nicht viel Rauschen bzw. nicht viele <a href="Ausrei%C3%9Fer" title="Ausreißer">Ausreißer</a> enthalten. Fehlerhafte Datenobjekte verschieben die berechneten Clusterzentren oft erheblich, und der Algorithmus hat keine Vorkehrungen gegen derartige Effekte (vgl. <a href="DBSCAN" title="DBSCAN">DBSCAN</a>, das „Noise“-Objekte explizit vorsieht).

<div class="mw-heading mw-heading2"><h2 id="Probleme">Probleme</h2></div>

k-Means ist ein leistungsfähiger Algorithmus, jedoch nicht ohne Schwachstellen. Ein k-Means-Algorithmus muss nicht die beste mögliche Lösung finden. Die gefundene Lösung hängt stark von den gewählten Startpunkten ab. Der einfachste Ansatz ist, den Algorithmus mehrmals hintereinander mit verschiedenen Startwerten zu starten und die beste Lösung zu nehmen. Es gibt aber auch viele Überlegungen, wie eine geeignete Verteilung der Startwerte erreicht werden kann. Zu nennen sind unter anderem k-means++, aber auch mit dem Ziehen kleiner Stichproben können die Clusterzentren vor dem Start von k-means angenähert werden. Außerdem macht es einen Unterschied, ob man beliebige Clusterzentren wählt, oder jeden Punkt einem beliebigen Cluster zuordnet und dann die Clusterzentren ermittelt.

Ein weiterer Nachteil ist, dass die Anzahl der Clusterzentren <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> im Voraus gewählt wird. Bei Verwendung eines ungeeigneten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> können sich komplett andere, unter Umständen unintuitive Lösungen ergeben. Bei einem „falschen“ <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> kann kein gutes Clustering erfolgen. Die Lösung ist, verschiedene Werte für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> zu probieren und dann ein geeignetes zu wählen, zum Beispiel mit Hilfe des <a href="Silhouettenkoeffizient" title="Silhouettenkoeffizient">Silhouettenkoeffizienten</a>, oder durch Vergleich der verschiedenen Clusteringkosten.

Gruppen in den Daten können sich, wie in dem gezeigten Schwertlilien-Beispiel, überlappen und nahtlos ineinander übergehen. In einem solchen Fall kann k-Means diese Gruppen nicht zuverlässig trennen, da die Daten nicht dem verwendeten Cluster-Modell folgen.

Des Weiteren sucht k-Means stets konvexe Cluster (bedingt durch die Minimierung des Abstandes zum Clusterschwerpunkt). Andere Algorithmen wie <a href="DBSCAN" title="DBSCAN">DBSCAN</a> können auch beliebig geformte „dichtebasierte“ Cluster finden. Was ebenfalls von k-Means nicht unterstützt wird, sind hierarchische Cluster (also Cluster, die wiederum eine Clusterstruktur aufweisen), wie sie beispielsweise mit <a href="OPTICS" title="OPTICS">OPTICS</a> gefunden werden können.

Als letztes wird in k-means jeder Punkt einem Cluster zugewiesen, es gibt keine Möglichkeit Ausreißer zu erkennen. Diese können das Ergebnis stark verfälschen. Abhilfe kann hier eine vorherige Noisereduktion schaffen, oder andere Algorithmen, wie <a href="DBSCAN" title="DBSCAN">DBSCAN</a>, die automatisch Noise erkennen.

<div class="mw-heading mw-heading2"><h2 id="Erweiterungen">Erweiterungen</h2></div>

<div class="mw-heading mw-heading3"><h3 id="K-Median">K-Median</h3></div>

Im k-Median-Algorithmus wird im Zuweisungschritt statt der euklidischen Distanz die <a href="Manhattan-Distanz" class="mw-redirect" title="Manhattan-Distanz">Manhattan-Distanz</a> verwendet. Im Updateschritt wird der <a href="Median" title="Median">Median</a> statt des <a href="Mittelwert" title="Mittelwert">Mittelwerts</a> verwendet.<a href="#cite_note-12">[12]</a><a href="#cite_note-13">[13]</a>

<div class="mw-heading mw-heading3"><h3 id="K-Means++">K-Means++</h3></div>

Der k-Means++-Algorithmus wählt die Cluster-Schwerpunkte nicht zufällig, sondern nach folgender Vorschrift:

<ol><li>Wähle als ersten Cluster-Schwerpunkt zufällig ein Objekt aus</li>

<li>Für jedes Objekt berechne den Abstand <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D(x)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/be208da111170920787fb435ff586d2377b43cc5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.063ex; height:2.843ex;" alt="{\displaystyle D(x)}" loading="lazy"> zum nächstgelegenen Cluster-Schwerpunkt</li>

<li>Wähle zufällig als nächsten Cluster-Schwerpunkt ein Objekt aus. Die Wahrscheinlichkeit, mit der ein Objekt ausgewählt wird, ist proportional zu <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D^{2}(x)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D^{2}(x)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a38f5b460a11e10caec89ade857e12ae00f8adde.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.117ex; height:3.176ex;" alt="{\displaystyle D^{2}(x)}" loading="lazy">, d. h. je weiter das Objekt von den bereits gewählten Cluster-Schwerpunkten entfernt ist, desto wahrscheinlicher ist es, dass es ausgewählt wird.</li>

<li>Wiederhole Schritt 2 und 3 bis <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> Cluster-Schwerpunkte bestimmt sind</li>

<li>Führe nun den üblichen k-Means Algorithmus aus</li></ol>

In der Regel konvergiert der nachfolgende k-Means Algorithmus in wenigen Schritten. Die Ergebnisse sind so gut wie bei einem üblichen k-Means-Algorithmus, jedoch ist der Algorithmus typischerweise fast doppelt so schnell wie der k-Means-Algorithmus.<a href="#cite_note-kanungo-14">[14]</a>

<div class="mw-heading mw-heading3"><h3 id="K-Medoids_(PAM)">K-Medoids (PAM)</h3></div>

Der Algorithmus PAM (Partitioning Around Medoids, Kaufman und Rousseeuw, 1990) – auch bekannt als k-Medoids<a href="#cite_note-15">[15]</a> – kann als Variante des k-Means Algorithmus interpretiert werden, die mit beliebigen Distanzen konvergiert.

<ol><li>Wähle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> Objekte als Cluster-Schwerpunkte (Medoid) aus</li>

<li>Ordne jedes Objekt dem nächsten Cluster-Schwerpunkt zu</li>

<li>Für jeden Cluster-Schwerpunkt und jeden Nicht-Cluster-Schwerpunkt vertausche die Rollen</li>

<li>Berechne für jede Vertauschung die Summe der Distanzen oder Unähnlichkeiten</li>

<li>Wähle als neue Cluster-Schwerpunkte die Vertauschung, die die kleinste Summe liefert</li>

<li>Wiederhole 2.–5. solange, bis sich die Cluster-Schwerpunkte nicht mehr ändern</li></ol>

In der ursprünglichen Version von PAM macht hierbei der erste Schritt – die Wahl der initialen Medoiden – einen großen Teil des Algorithmus aus. Da in jeder Iteration stets nur die beste Vertauschung durchgeführt wird, ist der Algorithmus nahezu deterministisch (bis auf exakt gleiche Distanzen). Dadurch ist der Algorithmus aber auch meist sehr langsam.

Während k-means die Summe der Varianzen minimiert, minimiert k-Medoids die Distanzen. Insbesondere kann dieser Algorithmus mit beliebigen Distanzfunktionen verwendet werden, und konvergiert dennoch garantiert.

<div class="mw-heading mw-heading2"><h2 id="Beispiel">Beispiel</h2></div>

Die folgenden Bilder zeigen exemplarisch einen Durchlauf eines k-Means-Algorithmus zur Bestimmung von drei Gruppen:

<td>

</td>

<td>Drei Clusterzentren wurden zufällig gewählt.

</td></tr>

<tr>

<td>

</td>

<td>Die durch Rechtecke repräsentierten Objekte (Datenpunkte) werden jeweils dem Cluster mit dem nächsten Clusterzentrum zugeordnet.

</td></tr>

<tr>

<td>

</td>

<td>Die Zentren (jeweilige Schwerpunkte) der Cluster werden neu berechnet.

</td></tr>

<tr>

<td>

</td>

<td>Die Objekte werden neu verteilt und erneut dem Cluster zugewiesen, dessen Zentrum am nächsten ist.

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Anwendung_in_der_Bildverarbeitung">Anwendung in der Bildverarbeitung</h2></div>

In der <a href="Bildverarbeitung" title="Bildverarbeitung">Bildverarbeitung</a> wird der k-Means-Algorithmus oft zur <a href="Segmentierung_(Bildverarbeitung)" title="Segmentierung (Bildverarbeitung)">Segmentierung</a> verwendet. Als Entfernungsmaß ist die euklidische Distanz häufig nicht ausreichend und es können andere Abstandsfunktionen, basierend auf <a href="Pixel#Pixelwerte" title="Pixel">Pixelintensitäten</a> und Pixelkoordinaten verwendet werden. Die Ergebnisse werden zur Trennung von Vordergrund und Hintergrund und zur <a href="Objekterkennung" title="Objekterkennung">Objekterkennung</a> benutzt. Der Algorithmus ist weit verbreitet und ist in gängigen Bildverarbeitungsbibliotheken wie <a href="OpenCV" title="OpenCV">OpenCV</a>, <a href="Scikit-image" title="Scikit-image">Scikit-image</a><a href="#cite_note-16">[16]</a> und <a href="Insight_Segmentation_and_Registration_Toolkit" title="Insight Segmentation and Registration Toolkit">itk</a> implementiert.

<div class="mw-heading mw-heading2"><h2 id="Software">Software</h2></div>

K-means und seine Varianten sind in verschiedener Open-Source-Software verfügbar.

<li><a href="Environment_for_DeveLoping_KDD-Applications_Supported_by_Index-Structures" title="Environment for DeveLoping KDD-Applications Supported by Index-Structures">ELKI</a> enthält die Varianten von Lloyd und MacQueen, dazu verschiedene Strategien für die Startwerte wie k-means++, und Varianten des Algorithmus wie k-medians, k-medoids und PAM.</li>

<li><a href="GNU_R" class="mw-redirect" title="GNU R">GNU R</a> enthält die Varianten von Hartigan, Lloyd und MacQueen, und zusätzliche Variationen im Erweiterungspaket „flexclust“.</li>

<li><a href="OpenCV" title="OpenCV">OpenCV</a> enthält eine auf Bildverarbeitung optimierte Version von k-means (inkl. k-means++ seeding)</li>

<li><a href="Scikit-learn" title="Scikit-learn">Scikit-learn</a> enthält k-means, inkl. Elkans Variante und k-means++.</li>

<li><a href="Waikato_Environment_for_Knowledge_Analysis" title="Waikato Environment for Knowledge Analysis">Weka</a> enthält k-means (inkl. k-means++ seeding) und die Erweiterung x-means.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>David MacKay: <cite style="font-style:italic">Information Theory, Inference and Learning Algorithms</cite>. Cambridge University Press, 2003, ISBN 0-521-64298-1, Chapter 20. An Example Inference Task: Clustering, S. 284–292 (<a rel="nofollow" class="external text" href="http://www.inference.phy.cam.ac.uk/mackay/itprnn/ps/284.292.pdf">inference.phy.cam.ac.uk</a> [PDF]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abookitem&rfr_id=info:sid/de.wikipedia.org:K-Means-Algorithmus&rft.atitle=Chapter+20.+An+Example+Inference+Task%3A+Clustering&rft.au=David+MacKay&rft.btitle=Information+Theory%2C+Inference+and+Learning+Algorithms&rft.date=2003&rft.genre=bookitem&rft.isbn=0521642981&rft.pages=284-292&rft.pub=Cambridge+University+Press" style="display:none"> </li>

<li>Gary Bradski, Adrian Kaehler: <cite style="font-style:italic">Learning OpenCV Computer Vision with the OpenCV Library</cite>. O’Reilly, 2001, ISBN 978-0-596-51613-0.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:K-Means-Algorithmus&rft.au=Gary+Bradski%2C+Adrian+Kaehler&rft.btitle=Learning+OpenCV+Computer+Vision+with+the+OpenCV+Library&rft.date=2001&rft.genre=book&rft.isbn=9780596516130&rft.pub=O%E2%80%99Reilly" style="display:none"> </li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

Gary Bradski, Adrian Kaehler: <cite style="font-style:italic">Learning OpenCV Computer Vision with the OpenCV Library</cite>. O’Reilly, 2001, ISBN 978-0-596-51613-0, S. 479–480.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:K-Means-Algorithmus&rft.au=Gary+Bradski%2C+Adrian+Kaehler&rft.btitle=Learning+OpenCV+Computer+Vision+with+the+OpenCV+Library&rft.date=2001&rft.genre=book&rft.isbn=9780596516130&rft.pages=479-480&rft.pub=O%E2%80%99Reilly" style="display:none">

</li>

J. B. MacQueen: <cite style="font-style:italic">Some Methods for classification and Analysis of Multivariate Observations</cite>. In: <cite style="font-style:italic">Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability</cite>. Band 1. University of California Press, 1967, S. 281–297 (<a rel="nofollow" class="external text" href="http://projecteuclid.org/euclid.bsmsp/1200512992">projecteuclid.org</a> [abgerufen am 7. April 2009]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:K-Means-Algorithmus&rft.atitle=Some+Methods+for+classification+and+Analysis+of+Multivariate+Observations&rft.au=J.+B.+MacQueen&rft.btitle=Proceedings+of+5th+Berkeley+Symposium+on+Mathematical+Statistics+and+Probability&rft.date=1967&rft.genre=book&rft.pages=281-297&rft.pub=University+of+California+Press&rft.volume=1" style="display:none">

</li>

<a href="Hugo_Steinhaus" title="Hugo Steinhaus">Hugo Steinhaus</a>: <cite class="lang" lang="fr" dir="auto" style="font-style:italic">Sur la division des corps matériels en parties</cite>. In: <cite class="lang" lang="fr" dir="auto" style="font-style:italic">Bull. Acad. Polon. Sci.</cite> 12. Auflage. Band 4, 1957, S. 801–804 (französisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:K-Means-Algorithmus&rft.atitle=Sur+la+division+des+corps+mat%C3%A9riels+en+parties&rft.au=Hugo+Steinhaus&rft.btitle=Bull.+Acad.+Polon.+Sci.&rft.date=1957&rft.edition=12&rft.genre=book&rft.pages=801-804&rft.volume=4" style="display:none">

</li>

S. P. Lloyd: <cite style="font-style:italic">Least square quantization in PCM</cite>. In: <cite style="font-style:italic">Bell Telephone Laboratories Paper</cite>. 1957.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:K-Means-Algorithmus&rft.atitle=Least+square+quantization+in+PCM&rft.au=S.+P.+Lloyd&rft.btitle=Bell+Telephone+Laboratories+Paper&rft.date=1957&rft.genre=book" style="display:none"> , später erst in einer Zeitschrift:

S. P. Lloyd: <cite style="font-style:italic">Least squares quantization in PCM</cite>. In: <cite style="font-style:italic"><a href="IEEE_Transactions_on_Information_Theory" title="IEEE Transactions on Information Theory">IEEE Transactions on Information Theory</a></cite>. 2. Auflage. Band 28, 1982, S. 129–137, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109/TIT.1982.1056489">10.1109/TIT.1982.1056489</a> (<a rel="nofollow" class="external text" href="http://www.cs.toronto.edu/~roweis/csc2515-2006/readings/lloyd57.pdf">cs.toronto.edu</a> [PDF; 1,3 MB; abgerufen am 15. April 2009]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:K-Means-Algorithmus&rft.atitle=Least+squares+quantization+in+PCM&rft.au=S.+P.+Lloyd&rft.btitle=IEEE+Transactions+on+Information+Theory&rft.date=1982&rft.doi=10.1109%2FTIT.1982.1056489&rft.edition=2&rft.genre=book&rft.pages=129-137&rft.volume=28" style="display:none">

</li>

E.W. Forgy: <cite style="font-style:italic">Cluster analysis of multivariate data: efficiency versus interpretability of classifications</cite>. In: <cite style="font-style:italic">Biometrics</cite>. 21. Auflage. 1965, S. 768–769.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:K-Means-Algorithmus&rft.atitle=Cluster+analysis+of+multivariate+data%3A+efficiency+versus+interpretability+of+classifications&rft.au=E.W.+Forgy&rft.btitle=Biometrics&rft.date=1965&rft.edition=21&rft.genre=book&rft.pages=768-769" style="display:none">

</li>

J.A. Hartigan: <cite style="font-style:italic">Clustering algorithms</cite>. John Wiley & Sons, 1975.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:K-Means-Algorithmus&rft.au=J.A.+Hartigan&rft.btitle=Clustering+algorithms&rft.date=1975&rft.genre=book&rft.pub=John+Wiley+%26+Sons" style="display:none">

</li>

J. A. Hartigan, M. A. Wong: <cite style="font-style:italic">Algorithm AS 136: A K-Means Clustering Algorithm</cite>. In: <cite style="font-style:italic">Journal of the Royal Statistical Society, Series C (Applied Statistics)</cite>. 1. Auflage. Band 28, 1979, S. 100–108, <a href="JSTOR" title="JSTOR">JSTOR</a>:<a rel="nofollow" class="external text" href="http://www.jstor.org/stable/2346830">2346830</a>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:K-Means-Algorithmus&rft.atitle=Algorithm+AS+136%3A+A+K-Means+Clustering+Algorithm&rft.au=J.+A.+Hartigan%2C+M.+A.+Wong&rft.btitle=Journal+of+the+Royal+Statistical+Society%2C+Series+C+%28Applied+Statistics%29&rft.date=1979&rft.edition=1&rft.genre=book&rft.pages=100-108&rft.volume=28" style="display:none">

</li>

Martin Ester, Jörg Sander: <cite style="font-style:italic">Knowledge Discovery in Databases: Techniken und Anwendungen</cite>. Springer, Berlin 2000, ISBN 3-540-67328-8.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:K-Means-Algorithmus&rft.au=Martin+Ester%2C+J%C3%B6rg+Sander&rft.btitle=Knowledge+Discovery+in+Databases%3A+Techniken+und+Anwendungen&rft.date=2000&rft.genre=book&rft.isbn=3540673288&rft.place=Berlin&rft.pub=Springer" style="display:none">

</li>

<li id="cite_note-9"><a href="#cite_ref-9">↑</a> David Arthur, Sergei Vassilvitskii: <cite style="font-style:italic">K-means++: The Advantages of Careful Seeding</cite>. In: <cite style="font-style:italic">Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms</cite>. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA 2007, ISBN 978-0-89871-624-5, S. 1027–1035 (<a rel="nofollow" class="external text" href="http://theory.stanford.edu/~sergei/slides/BATS-Means.pdf">stanford.edu</a> [PDF; abgerufen am 27. März 2015]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:K-Means-Algorithmus&rft.atitle=K-means%2B%2B%3A+The+Advantages+of+Careful+Seeding&rft.au=David+Arthur%2C+Sergei+Vassilvitskii&rft.btitle=Proceedings+of+the+Eighteenth+Annual+ACM-SIAM+Symposium+on+Discrete+Algorithms&rft.date=2007&rft.genre=book&rft.isbn=9780898716245&rft.pages=1027-1035&rft.place=Philadelphia%2C+PA%2C+USA&rft.pub=Society+for+Industrial+and+Applied+Mathematics" style="display:none">

</li>

<li id="cite_note-10"><a href="#cite_ref-10">↑</a> T. Kanungo, D. M. Mount, N. S. Netanyahu, C. D. Piatko, R. Silverman, A. Y. Wu: <cite class="lang" lang="en" dir="auto" style="font-style:italic">An efficient k-means clustering algorithm: Analysis and implementation</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">IEEE Trans. Pattern Analysis and Machine Intelligence</cite>. Vol. 24, 2002, S. 881–892, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109/TPAMI.2002.1017616">10.1109/TPAMI.2002.1017616</a> (englisch, <a rel="nofollow" class="external text" href="http://www.cs.umd.edu/~mount/Papers/pami02.pdf">umd.edu</a> [PDF; abgerufen am 24. April 2009]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:K-Means-Algorithmus&rft.atitle=An+efficient+k-means+clustering+algorithm%3A+Analysis+and+implementation&rft.au=T.+Kanungo%2C+D.+M.+Mount%2C+N.+S.+Netanyahu%2C+...&rft.btitle=IEEE+Trans.+Pattern+Analysis+and+Machine+Intelligence&rft.date=2002&rft.doi=10.1109%2FTPAMI.2002.1017616&rft.genre=book&rft.pages=881-892&rft.volume=Vol.+24" style="display:none">

</li>

C. Elkan: <cite style="font-style:italic">Using the triangle inequality to accelerate k-means</cite>. In: <cite style="font-style:italic">Proceedings of the Twentieth International Conference on Machine Learning (ICML)</cite>. 2003 (<a rel="nofollow" class="external text" href="http://www-cse.ucsd.edu/~elkan/kmeansicml03.pdf">ucsd.edu</a> [PDF; 88 kB]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:K-Means-Algorithmus&rft.atitle=Using+the+triangle+inequality+to+accelerate+k-means&rft.au=C.+Elkan&rft.btitle=Proceedings+of+the+Twentieth+International+Conference+on+Machine+Learning+%28ICML%29&rft.date=2003&rft.genre=book" style="display:none">

</li>

<li id="cite_note-12"><a href="#cite_ref-12">↑</a> A. K. Jain, R. C. Dubes: Algorithms for Clustering Data, Prentice-Hall, 1981.

</li>

<li id="cite_note-13"><a href="#cite_ref-13">↑</a> P. S. Bradley, O. L. Mangasarian, W. N. Street: Clustering via Concave Minimization. In: M. C. Mozer, M. I. Jordan, T. Petsche (Hrsg.): Advances in Neural Information Processing Systems, vol. 9, MIT Press, Cambridge MA 1997, S. 368–374.

</li>

T. Kanungo, D. Mount, N. Netanyahux, C. Piatko, R. Silverman, A. Wu <a rel="nofollow" class="external text" href="http://www.cs.umd.edu/~mount/Projects/KMeans/kmlocal-cgta.pdf">A Local Search Approximation Algorithm for k-Means Clustering.</a> (PDF; 170 kB) In: Computational Geometry: Theory and Applications, 2004.

</li>

<li id="cite_note-15"><a href="#cite_ref-15">↑</a> S. Vinod: <cite style="font-style:italic">Integer programming and the theory of grouping</cite>. In: <cite style="font-style:italic">Journal of the American Statistical Association</cite>. Band 64, 1969, S. 506--517.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:K-Means-Algorithmus&rft.atitle=Integer+programming+and+the+theory+of+grouping&rft.au=S.+Vinod&rft.btitle=Journal+of+the+American+Statistical+Association&rft.date=1969&rft.genre=book&rft.pages=506--517&rft.volume=64" style="display:none">

</li>

<li id="cite_note-16"><a href="#cite_ref-16">↑</a> <a rel="nofollow" class="external text" href="http://scikit-image.org/docs/dev/api/skimage.segmentation.html">Module: segmentation — skimage docs.</a> Abgerufen am 8. September 2018 (englisch).<span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3AK-Means-Algorithmus&rft.title=Module%3A+segmentation+%E2%80%94+skimage+docs&rft.description=Module%3A+segmentation+%E2%80%94+skimage+docs&rft.identifier=http%3A%2F%2Fscikit-image.org%2Fdocs%2Fdev%2Fapi%2Fskimage.segmentation.html&rft.language=en">

</li>

<li id="cite_note-17"><a href="#cite_ref-17">↑</a> <a rel="nofollow" class="external text" href="http://dlib.net/kkmeans_ex.cpp.html">dlib C++ Library - kkmeans_ex.cpp.</a> Abgerufen am 8. Januar 2019.<span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3AK-Means-Algorithmus&rft.title=dlib+C%2B%2B+Library+-+kkmeans_ex.cpp&rft.description=dlib+C%2B%2B+Library+-+kkmeans_ex.cpp&rft.identifier=http%3A%2F%2Fdlib.net%2Fkkmeans_ex.cpp.html">

</li>

</ol></div></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-03-27" href="https://de.wikipedia.org/wiki/?title=K-Means-Algorithmus&oldid=254606489">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>